package com.ken.algorithms.stack;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * <ul>
 * <li>Title: MainCD15</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/22 14:39
 */
public class MainCD15 {

    public static void main(String[] args) throws Exception {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] arguments = reader.readLine().split(" ");
        int n = Integer.parseInt(arguments[0]);
        int w = Integer.parseInt(arguments[1]);
        int[] arr = new int[n];
        String[] elements = reader.readLine().split(" ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(elements[i]);
        }

        int[]  maxW =    getMaxWindow(arr,w);

        System.out.println(Arrays.toString(maxW));
    }


    private static int[] getMaxWindow(int[] arr, int w) {
        int[] res = new int[arr.length-w+1];//产生的结果
        int index = 0;
        //单调递减  取队头 没错（最大)
        LinkedList<Integer> qmax= new LinkedList<Integer>();

        for (int i = 0; i < arr.length; i++) {
            // 后面的数 大于 当前栈中的数 队尾元素出栈
            while (!qmax.isEmpty() &&  arr[i] >= arr[ qmax.peekLast()] ){
                qmax.pollLast();
            }
            // 最后把这个 大的元素放入
            qmax.addLast(i);
            // 队头元素失效了
            if(qmax.peekFirst()==i-w){
                qmax.pollFirst();// 移除队头的元素
            }
            // 队头就是当前窗口的最大元素
            if(i>=w-1){
                res[index++] = arr[qmax.peekFirst()];
            }

        }
        return res;
    }

   /* private static int[] getMaxWindow(int[] arr, int w) {
        int[] res = new int[arr.length-w+1];//产生的结果
        int index = 0;
        //单调递减  取队头 没错（最大)
        Stack<Integer> qmax= new Stack<>();
        int curMax = 0 ;
        int headInd = -1;

        for (int i = 0; i < arr.length; i++) {

            if(qmax.isEmpty()){
                qmax.push(i);
                curMax = arr[i];
                headInd = i;
            }
            // 2. 当前元素 < 队尾元素，直接入队
            else if(arr[i] < arr[ qmax.peek()]){
                qmax.push(i);
                curMax = Math.max(arr[i],curMax);
            }
            else{
                // 后面的数 大于 当前栈中的数 队尾元素出栈
                while (!qmax.isEmpty() &&  arr[i] >= arr[qmax.peek()] ){
                    //头部元素一出栈
                    if(qmax.peek()==headInd){
                        headInd = -1;
                    }
                    qmax.pop();
                }
                // 最后把这个 大的元素放入
                qmax.push(i);
                curMax = Math.max(arr[i],curMax);
                headInd = headInd==-1?i:headInd;
            }

            // 队头元素失效了
            if(headInd==i-w){
                if(curMax==arr[qmax.peek()]){
                    curMax= -1;
                }
                qmax.pop();// 移除队头的元素
            }

            // 队头就是当前窗口的最大元素
            if(i>=w-1){
                res[index++] =curMax;
            }

        }

        return res;
    }*/

  /*  private static int[] getMaxWindow(int[] arr, int w) {
        int[] res = new int[arr.length-w+1];//产生的结果
        int index = 0;
        //单调递减  取队头 没错（最大)
        LinkedList<Integer> qmax= new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {

            if(qmax.isEmpty()){
                //list.add(i);
                qmax.addLast(i);
            }
            // 2. 当前元素 < 队尾元素，直接入队
            else if(arr[i] < arr[ qmax.peekLast()]){
                qmax.addLast(i);
            }

            else{
                // 后面的数 大于 当前栈中的数 队尾元素出栈
                while (!qmax.isEmpty() &&  arr[i] >= arr[ qmax.peekLast()] ){
                    qmax.pollLast();
                }
                // 最后把这个 大的元素放入
                qmax.addLast(i);
            }

            // 队头元素失效了
            if(qmax.peekFirst()==i-w){
                qmax.pollFirst();// 移除队头的元素
            }

            // 队头就是当前窗口的最大元素
            if(i>=w-1){
                res[index++] = arr[qmax.peekFirst()];
            }

        }

        return res;
    }*/


}
